# 57/100 回溯-电话号码的字母组合
# leetcode第46题: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/3

from leetcode import test


def letterCombinations(digits: str) -> list[str]:
    # mapping = {"2": ["a", "b", "c"], "3": ["d", "e", "f"], "4": ["g", "h", "i"],
    #            "5": ["j", "k", "l"], "6": ["m", "n", "o"], "7": ["p", "q", "r", "s"],
    #            "8": ["t", "u", "v"], "9": ["w", "x", "y", "z"], }

    mapping = {"2": "abc", "3": "def", "4": "ghi",
               "5": "jkl", "6": "mno", "7": "pqrs",
               "8": "tuv", "9": "wxyz", }

    n = len(digits)
    if n < 1:
        return []

    res = []

    def backtracking(path, index):
        if len(digits) == len(path):
            res.append(path)
            return
        for word in mapping[digits[index]]:
            path += word
            backtracking(path, index + 1)
            path = path[:-1]

    backtracking("", 0)
    return res


if __name__ == '__main__':
    inp = [{"digits": "23"}, {"digits": "2"}, ]

    out = [
        ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"],
        ["a", "b", "c"]
    ]

    test.test_function(letterCombinations, inp, out)
